學習資源

https://labuladong.online/algo/data-structure-basic/use-case-of-dfs-bfs/#为什么-dfs-常用来寻找所有路径

學習記錄

今天是學習的第 23 天，主要學習了 DFS 的適用場景：

為什麼 DFS 常用來尋找所有路徑

因為 DFS 的遍歷方式本身就是「一條路走到底」，每次遞歸都沿著一條樹枝深入，直到葉子節點才回溯。這個特性就和「路徑」的概念相互契合。

核心原理

DFS 尋找所有路徑的關鍵在於回溯機制：

• 前序位置：進入節點時記錄路徑
• 到達終點：收集完整路徑
• 後序位置：離開節點時撤銷選擇（回溯）

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 輸入二叉樹的根節點，返回所有根節點到葉子節點的路徑
var findAllPaths = function(root) {
    // res 用來存放所有路徑
    const res = [];
    // path 用來存放當前正在遍歷的路徑
    const path = [];

    const traverse = (root) => {
        if (root === null) {
            return;
        }

        // 前序位置進入節點時，把節點值加入 path
        path.push(root.val);

        if (root.left === null && root.right === null) {
            // 到達葉子節點，找到一條路徑
            res.push([...path]);
        }

        traverse(root.left);
        traverse(root.right);

        // 後序位置離開節點時，把節點值從 path 中移除
        path.pop();
    };

    traverse(root);

    return res;
};

// 建立一棵滿二叉樹（高度為 3）
//        1
//      /   \
//     2     3
//    / \   / \
//   4   5 6   7

const root = new TreeNode(1);

root.left = new TreeNode(2);
root.right = new TreeNode(3);

root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

const result = findAllPaths(root);
// 取得所有的路徑
// [1, 2, 4]
// [1, 2, 5]
// [1, 3, 6]
// [1, 3, 7]

學習總結

• DFS 常用來尋找所有路徑，因為 DFS 的遍歷方式本身就是「一條路走到底」